package java学习.leetcode.editor.cn;

import java.util.Arrays;

/**
 * @author 刘世锦
 * 2022-10-19 23:03:28	 当前时间
 */
//给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
//如果 needle 不是 haystack 的一部分，则返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：haystack = "sadbutsad", needle = "sad"
//输出：0
//解释："sad" 在下标 0 和 6 处匹配。
//第一个匹配项的下标是 0 ，所以返回 0 。
// 
//
// 示例 2： 
//
// 
//输入：haystack = "leetcode", needle = "leeto"
//输出：-1
//解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= haystack.length, needle.length <= 104 
// haystack 和 needle 仅由小写英文字符组成 
// 
// Related Topics 双指针 字符串 字符串匹配 
// 👍 1618 👎 0

public class 找出字符串中第一个匹配项的下标{
	public static void main(String[] args) {
		Solution solution = new 找出字符串中第一个匹配项的下标().new Solution();
		String haystack = "sadbutsad", needle = "sad";
		System.out.println(solution.strStr(haystack, needle));

	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	//给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
//如果 needle 不是 haystack 的一部分，则返回 -1 。
//	               0 1 2 3 4 5 6 7 8 9
//	                     i
//输入：haystack = "b u s c d s a d d ",
//	                 j
//       needle = "s a d "
//
//	               0 1 2 3 4 5 6 7 8 9 10 11
//	                                     i
//输入：haystack = "s a s a s a s a s a d ",
//	                     j
//       needle = "s a d "
//
//输出：0
//	双指针
	public int strStr1(String haystack, String needle) {
		if (haystack.length()<needle.length()){
			return -1;
		}
		int i = 0,j=0,hl = haystack.length(),nl = needle.length();
		while (i<hl&&j<nl){

			if (haystack.charAt(i)==needle.charAt(j)){
				i++;j++;
			}else {
				i=i-j+1;
				j = 0;
			}

		}
		if (j==nl){
			return i-j;
		}else {
			return -1;
		}
	}

	// KMP。用处： 在一个串中查找是否出现过另一个串

	/**
	 * 1. 求next数组 ： next[i]: 0~i 的前缀、后缀 相同的字符串的长度
	 * 2. 判断若 相等。j++；否则 j返回到 前一个字符的next[]值： next[j-1]
	 *
	 */
	public void getNext(String s,int[] next){
		next[0] = 0; int j = 0;
//		i为什么从1开始： next[0] 前缀，后缀 都是空串，故为0，不需要计算
		for (int i = 1; i < s.length(); i++) {
			while (j>0&& s.charAt(i)!=s.charAt(j)){
				j = next[j-1];
			}
			if (s.charAt(i)==s.charAt(j)){
				j++;
			}
			next[i] = j;
			// 最后 i++;
		}
	}
	public int strStr(String haystack, String needle) {
		int [] next = new int[needle.length()];
		getNext(needle,next);
		System.out.println(Arrays.toString(next));
		int j = 0;
		for (int i = 0; i < haystack.length(); i++) {
			while (j>0&&haystack.charAt(i)!=needle.charAt(j)){
				j = next[j-1];
			}
			if (haystack.charAt(i)==needle.charAt(j)){
				j++;
			}
			if (j==needle.length()){
				return i-j+1;
			}
			// 最后 i++;
		}
		return -1;
	}


//	纯纯api。
    public int strStr3(String haystack, String needle) {
		return haystack.indexOf(needle);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
